Given the edges of a directed graph where edges[i] = [ai, bi] indicates there is an edge between nodes ai and bi, and two nodes source and destination of this graph, determine whether or not all paths starting from source eventually, end at destination, that is:
- At least one path exists from the
sourcenode to thedestinationnode - If a path exists from the
sourcenode to a node with no outgoing edges, then that node is equal todestination. - The number of possible paths from
sourcetodestinationis a finite number.
Return true if and only if all roads from source lead to destination.
Example 1:
Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2 Output: false Explanation: It is possible to reach and get stuck on both node 1 and node 2.
Example 2:
Input: n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3 Output: false Explanation: We have two possibilities: to end at node 3, or to loop over node 1 and node 2 indefinitely.
Example 3:
Input: n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3 Output: true
Example 4:
Input: n = 3, edges = [[0,1],[1,1],[1,2]], source = 0, destination = 2 Output: false Explanation: All paths from the source node end at the destination node, but there are an infinite number of paths, such as 0-1-2, 0-1-1-2, 0-1-1-1-2, 0-1-1-1-1-2, and so on.
Example 5:
Input: n = 2, edges = [[0,1],[1,1]], source = 0, destination = 1 Output: false Explanation: There is infinite self-loop at destination node.
Constraints:
1 <= n <= 1040 <= edges.length <= 104edges.length == 20 <= ai, bi <= n - 10 <= source <= n - 10 <= destination <= n - 1- The given graph may have self-loops and parallel edges.
Average Rating: 5.00 (13 votes)
Solution
Overview
Let's try to boil the problem down to simpler, more commonly understandable terms.
- We are given a directed graph.
- Also, as inputs we are provided a
sourceand adestination. - We need to tell if all the paths from the
sourcelead to thedestinationand and we can split this into a few criteria.- If a path exists from the
sourcenode to a node with no outgoing edges, then that node must be equal todestination. Here, we simply need to see that if a node does not have any neighbors in theadjacency liststructure, then it has to be thedestinationor else we returnfalse. - The number of possible paths from
sourcetodestinationis a finite number. This simply means that the graph is actually atree. Or in other words, there are no cycles in the graph. If there is a cycle in the graph, there would be an infinite number of paths from the source to the destination, as each would go around the cycle a different number of times.
- If a path exists from the
Thus, the problem simply boils down to two things which we need to check during our graph traversal algorithm. We need to detect any cycles in the traversal and return false if there are any. Also, we need to ensure that if there is a leaf node encountered during the traversal, it is the destination node.
The common strategies to traverse a graph are Breadth-First Search (a.k.a. BFS) and Depth-First Search (a.k.a. DFS). If one is not familiar with the concepts of BFS and DFS, we have an Explore card called Queue & Stack where we cover the BFS traversal as well as the DFS traversal. In this article, we'll be assuming that you're already familiar with these concepts.
Approach: Depth First Search
Intuition
This is one of the most common graph traversal techniques out there which makes use of the stack data structure. As mentioned in the overview section above, we simply need to run a graph traversal algorithm and check for two basic conditions. It is easy enough to check for a leaf node since the adjacency list entry for that node would not contain any neighbors. So our first condition can be easily checked i.e. if we encounter a leaf node, we check its equality to the destination node.
As for cycle detection, there are multiple ways one can go about modifying the standard DFS algorithm. We will be following the node-coloring variant of the algorithm which is explained in the Introduction to Algorithms (CLRS) book. The idea is to do DFS of a given graph and while doing traversal, assign one of the below three colors to every vertex. According to the algorithm mentioned in the book, there are three different colors we can assign a node:
WHITE ~ Vertex is not processed yet. Initially, all vertices are WHITE.
GRAY ~ Vertex is being processed (DFS for this vertex has started, but not finished which means that all descendants (in DFS tree) of this vertex are not processed yet (or this vertex is in the function call stack).
Figure 1. Highlighting an edge to a GRAY node thus creating a cycle in the graph.
BLACK ~ Vertex and all its descendants are processed.
Figure 2. Highlighting an edge to a BLACK node.
While doing DFS, if an edge is encountered from current vertex to a GRAY vertex, then this edge is a back edge and hence there is a cycle. A GRAY node represents a node whose processing is still ongoing. Thus, if a descendent eventually leads back to a node whose processing is ongoing, it ends up creating a cycle in the directed graph and we call the edge leading back to a GRAY node as a backward edge.
Algorithm
- Create a recursive function
leadsToDestthat takes the current node that needs to be processed and thecolor array. - We check if this node has any neighbors or not. If it doesn't then we return
trueorfalsebased on whether this node equals thedestinationnode. - There are three possibilities for the color of this current node.
- If it is
BLACK, do nothing; we've already processed it. - If it is
WHITE, then mark it asGRAYsince we are starting the processing of the graph rooted at this node. - Otherwise, if it is
GRAY, then returnfalseas we have discovered a backward edge, and hence a cycle.
- If it is
- Traverse all the adjacent nodes and for each of them call the recursive function for that node. If the function returns false, return
false. - Mark the current Node as
BLACKand returntrue.
Complexity Analysis
- Time Complexity: Typically for an entire DFS over an input graph, it takes O(V+E) where V represents the number of vertices in the graph and likewise, E represents the number of edges in the graph. In the worst case E can be O(V2) in case each vertex is connected to every other vertex in the graph. However even in the worst case, we will end up discovering a cycle very early on and prune the recursion tree. If we were to traverse the entire graph, then the complexity would be O(V2) as the O(E) part would dominate. However, due to pruning and backtracking in case of cycle detection, we end up with an overall time complexity of O(V).
- Space Complexity: O(V+E) where O(E) is occupied by the adjacency list and O(V) is occupied by the recursion stack and the color states.
Why not Breadth-First Search?
From this Stack Overflow answer:
A BFS could be reasonable if the graph is undirected (be my guest at showing an efficient algorithm using BFS that would report the cycles in a directed graph!), where each cross edge defines a cycle (edge going from a node to an already visited node). If the cross edge is
{v1, v2}, and the root (in the BFS tree) that contains those nodes isr, then the cycle isr ~ v1 - v2 ~ r(~ is a path, - a single edge), which can be reported almost as easily as in DFS.
The only reason to use a BFS would be if you know your (undirected) graph is going to have long paths and small path cover (in other words, deep and narrow). In that case, BFS would require proportionally less memory for its queue than DFS' stack (both still linear of course).
In all other cases, DFS is clearly the winner.
There are some approaches mentioned in the discussion section that make use of BFS and Topological sorting. However, they don't cover all the test cases and also, they involve a lot of modification to these standard algorithms. Therefore, they aren't sensible approaches to take in an interview setting.
April 8, 2021 2:01 AM
Wouldn't use a boolean mask for each node indicating whether it has been visited more intuitive? Gray and black nodes are not very common (personal experience though).
June 2, 2021 12:49 AM
Your explanation about why DFS over BFS is just priceless.
Many thanks!
6 hours ago
the standard way of cycle detection is a simple boolean[] array
https://leetcode.com/problems/all-paths-from-source-lead-to-destination/discuss/1290817/Java-or-DFS-or-Cycle-detection-or-with-comments
i am confused, if "If a path exists from the source node to a node with no outgoing edges, then that node is equal to destination." is correct, why Example 1 is false? It has two destinations and all nodes from source lead to destinations (two different destinations)
Also, I wouldn't say that if this is True, then the graph is a Tree structure, in a tree the only common node between the paths from root to leafs is the root. In other word, tree nodes don't have more than one parent.
I think the coloring explanation is too much and kind of confusing for this case in DFS, I prefer a boolean or a set approach, this is my solution in python:
class Solution:
def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
# Creating the graph
g = [set() for _ in range(n)]
for edge in edges:
g[edge[0]].add(edge[1])
# destination should not point to any other node
if len(g[destination]) > 0:
return False
seen = set()
def dfs(node):
# If can't reach any other node, node has to be destination
if len(g[node]) == 0:
return node == destination
for neighborg in g[node]:
if neighborg in seen:
# Cycle Found!!!
return False
seen.add(neighborg)
if not dfs(neighborg):
# We stop if the path could not reach destination
return False
seen.remove(neighborg)
# Congratulations all paths reaches destination
return True
return dfs(source)
This simply means that the graph is actually a tree. Or in other words, there are no cycles in the graph. If there is a cycle in the graph, there would be an infinite number of paths from the source to the destination, as each would go around the cycle a different number of times
I don't think this is entirely true as currently stated - let's imagine there is a reachable loop after all paths from the source to destination. Such loop does not seem to contradict any of the conditions on it's own. An example:
4
[[0, 1], [1, 2], [2, 3], [3, 2]]
0
1
In here, we have a [2, 3] loop reachable from the destination, but there is still a finite number of paths from 0 to 1 and none of the nodes are leaves.
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 06/23/2021 08:33 | Accepted | 72 ms | 32.9 MB | cpp |
xxxxxxxxxx};# define NOT_VISITED -1# define PROCESSING 0# define PROCESSED 1// processing means we are currently examining the node// processed means we have examined and are sure all paths from current node leads to destinationclass Solution {public: bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) { vector<vector<int>> adjList(n); vector<int> visited(n, NOT_VISITED); for(auto e : edges) { adjList[e[0]].push_back(e[1]); } return dfs(adjList, visited, source, destination); } private: bool dfs(vector<vector<int>>& adjList, vector<int>& visited, int i, int destination) { // id adjlist is empty for some node, it means it does not have outgoing edges (destination node). if(adjList[i].empty()) return i == destination; if(visited[i] != NOT_VISITED) return visited[i]; visited[i] = PROCESSING; for(auto neigh : adjList[i]) { if(dfs(adjList, visited, neigh, destination) == false) return false; } visited[i] = PROCESSED; return true; }};
